package leetcode.链表;

/**
 * 合并K个排序链表
 */
public class Test23合并K个排序链表 {

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode l3 = new ListNode(0);
        ListNode head = l3;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                ListNode newNode = new ListNode(l1.val);
                l3.next = newNode;
                l3 = l3.next;
                l1 = l1.next;
            } else {
                ListNode newNode = new ListNode(l2.val);
                l3.next = newNode;
                l3 = l3.next;
                l2 = l2.next;
            }
        }
        while (l1 != null) {
            ListNode newNode = new ListNode(l1.val);
            l3.next = newNode;
            l3 = l3.next;
            l1 = l1.next;
        }
        while (l2 != null) {
            ListNode newNode = new ListNode(l2.val);
            l3.next = newNode;
            l3 = l3.next;
            l2 = l2.next;
        }
        return head.next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return new ListNode(0).next;
        }

        if (lists.length == 1) {
            return lists[0];
        }
        ListNode l1 = lists[0];

        // 思路来源于合并两个排序链表，每两个一合并，将 k 个合并完
        for (int i = 1; i < lists.length; i++) {
            ListNode l2 = lists[i];
            l1 = mergeTwoLists(l1, l2);

        }
        return l1;
    }
}
